BZOJ 2288 生日礼物

Description

ftiasch 18岁生日的时候,lqp18_31给她看了一个神奇的序列 A1, A2, …, AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。
自然地,ftiasch想要知道选择元素之和的最大值。你能帮助她吗?

Input

第1行,两个整数 N (1 ≤ N ≤ 105) 和 M (0 ≤ M ≤ 105), 序列的长度和可以选择的部分。
第2行, N 个整数 A1, A2, …, AN (0 ≤ |Ai| ≤ 104), 序列。

Output

一个整数,最大的和。

Sample Input

5 2
2 -3 2 -1 2

Sample Output

5

Solution

区的区间是连续的,显然同符号的可以先合并在一起
那么序列变成了正负交替出现的序列
统计一下正数的个数,如果小于可选择数量,直接输出
否则需要贪心解决
可以将各个元素的绝对值加入堆中,每次取出一个最小的元素
将它和它左右两个元素合并,将它们的和加入堆中,并标记删除这三个元素
因为取得是最小的,保证了合并之后符号相反,序列仍保持正负交替出现
这样选择的实际意义是什么呢?
如果这个值是正的,代表放弃这一段区间元素和
如果这个值是负的,代表选择这段区间,使得左右正区间合并
结果都是少选一段区间,代价都是这个元素的绝对值

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>

#define maxn 100000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

priority_queue<pii,vector<pii>,greater<pii> > q;
int vis[maxn];
int pre[maxn],next[maxn];
int a[maxn],sum[maxn];
int num,tot,cnt=1;
int n,m,ans;

void del(int x)
{

next[pre[x]]=next[x];
pre[next[x]]=pre[x];
}

void add(int x,int t)
{

pre[next[x]]=t;
pre[t]=x,next[t]=next[x];
next[x]=t;
}

void deal(int x)
{

int l=pre[x],r=next[x],v;
vis[l]=vis[r]=vis[x]=1;
v=a[l]+a[r]+a[x];
a[++num]=v;
del(x);
if( l!=0 ) del(l);
if( r!=0 ) del(r);
if( l==0 ) add(l,num);
else add(pre[l],num);
q.push(make_pair(abs(v),num));
}

void solve()
{

num=cnt;
for(int i=m+1;i<=tot;i++){
pii sd;
while( true ){
sd=q.top(),q.pop();
if( a[sd.second]<0 && ( sd.second==next[0] || sd.second==pre[0] ) )
continue;
else if( !vis[sd.second] ) break;
}
deal(sd.second);
ans-=sd.first;
}
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("2288.in","r",stdin);
freopen("2288.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int t;
scanf("%d",&t);
if( a[cnt]*t>=0 ) a[cnt]+=t;
else a[++cnt]=t;
}
for(int i=1;i<=cnt;i++)
if( a[i]>0 ) tot++,ans+=a[i];
if( tot<=m ){
printf("%d",ans);
return 0;
}
for(int i=1;i<=cnt;i++)
q.push(make_pair(abs(a[i]),i));
for(int i=0;i<=cnt;i++)
pre[i]=i-1,next[i]=i+1;
pre[0]=cnt,next[cnt]=0;
solve();
printf("%d",ans);
return 0;
}